package com.monday.dynamic.programming;

/**
 * 0-1 背包问题
 * 对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
 */
public class ZeroOnePackage {

    private static int [] items = new int[]{3, 4, 13, 6,};
    private static int maxWeightOfBackpack = 11;

    public static void main(String[] args) {
        int result = maxWeight();
        System.out.println(result);
    }

    /**
     * 枚举法, 时间复杂度: 2^n,每个物品都有不装与装两种可能性。
     *
     */
    private static int maxWeight() {
        if (items == null || maxWeightOfBackpack <= 0) {
            return 0;
        }
        return f(0, 0);
    }

    /**
     * @param currIndex     : 当前物品的索引
     * @param currWeight    : 现在背包的重量
     */
    private static int f(int currIndex, int currWeight) {
        // 判断退出条件
        if (currIndex >= items.length) {
            return currWeight;
        }

        // 装当前物品
        int containCurrent = f(currIndex + 1, items[currIndex] + currWeight);

        // 不装当前物品
        int notContainCurrent = f(currIndex + 1, currWeight);

        // 两者都超过背包能承受重量, 直接返回原来背包的重量
        if (containCurrent > maxWeightOfBackpack && notContainCurrent > maxWeightOfBackpack) {
            return currWeight;
        }

        // 两者都小于背包能承受重量, 返回大者
        if (containCurrent <= maxWeightOfBackpack && notContainCurrent <= maxWeightOfBackpack) {
            return Math.max(containCurrent, notContainCurrent);
        }

        // 否则返回小于背包能承受重量
        return containCurrent <= maxWeightOfBackpack ? containCurrent : notContainCurrent;
    }

}
